There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...) that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power of$\mathcal {L}$has order-type$\omega + (...) \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$. (shrink)